package jjn.round1;

/**
 * @author Jjn
 * @since 2022/11/9 23:19
 */
public class LeetCode416_PartitionEqualSubsetSum {
    public boolean canPartition(int[] nums) {
        int sum = 0;
        // 求个和，非偶数的排除
        if (nums.length <= 1) {
            return false;
        }
        int maxNum = Integer.MIN_VALUE;
        for (int num : nums) {
            sum += num;
            maxNum = Math.max(num, maxNum);
        }
        if (sum % 2 == 1) {
            return false;
        }
        // 某些数超过一半，此时肯定不可能了
        int half = sum / 2;
        if (maxNum > half) {
            return false;
        }
        boolean[][] dp = new boolean[nums.length][half + 1];
        for (int i = 0; i < nums.length; i++) {
            dp[i][0] = true;
        }
        dp[0][nums[0]] = true;
        for (int i = 1; i < nums.length; i++) {
            int num = nums[i];
            for (int j = 1; j <= half; j++) {
                if (j > num) {
                    dp[i][j] = dp[i - 1][j] | dp[i - 1][j - num];
                } else {
                    dp[i][j] = dp[i - 1][j];
                }
            }
        }
        return dp[nums.length - 1][half];
    }
}
